package com.linzm.leetcode.mid.tree.层次遍历;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author zimingl
 * @Date 2023/2/20 23:52
 * @Description: 填充每个节点的下一个右侧节点指针 II
 */
public class Connect117 {
    public static void main(String[] args) {
        Connect117 connect117 = new Connect117();
        TreeNode connect = connect117.connect(TreeNode.getTree());
        System.out.println(connect);
    }

    public TreeNode connect(TreeNode root) {
        if (root == null) return root;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode cur = queue.poll();
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
            while (size > 1) {
                TreeNode next = queue.poll();
                if (next.left != null) queue.offer(next.left);
                if (next.right != null) queue.offer(next.right);
                cur.next = next;
                cur = next;
                size--;
            }
        }
        return root;
    }
}
